package leetcode.top100;

import leetcode.a_总结分布.Code09_单调栈问题;

import java.util.Stack;

/**
 * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [
 * ["1","0","1","0","0"],
 * ["1","0","1","1","1"],
 * ["1","1","1","1","1"],
 * ["1","0","0","1","0"]
 * ]
 * 输出: 6
 * <p>
 * 见{@link Code11_GetMaxWater_装水最多的容器}
 * 见{@link Code42_MaxWater_接雨水}
 * 见{@link Code85_MaxRectangleArea2}
 * <p>
 * <p>
 * 单调栈相关问题{@link Code09_单调栈问题}
 *
 * @date 2020/4/6 21:48
 */
public class Code85_MaxRectangleArea2 {

    /**
     * 方式1：暴力。来到位置(i,j)，先计算所处行能围城的最大面积，
     * 然后往上扩。计算面积。重复已上过程。
     * m[i][j]表示在第i行下，j位置处连续1的个数。
     * 注意每行第一个也就是第1列，为1.
     * <p>
     * 时间O(m²n)，空间O(mn)
     */
    public int largestRectangleArea1(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] m = new int[row][col];
        int area = 0;
        //每行遍历
        for (int i = 0; i < row; i++) {
            //单独处理第i行的所有列
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    //如果是第一列，那么就记为1，否则为前一个连续1个数 +1
                    m[i][j] = (j == 0 ? 1 : m[i][j - 1] + 1);
                } else {
                    m[i][j] = 0;
                }
                //记录当前行产生长，也就是面积
                int length = m[i][j];
                //从当前行，往上扩
                for (int k = i; k >= 0; k--) {
                    length = Math.min(length, m[k][j]);
                    area = Math.max(area, length * (i - k + 1));
                }

            }

        }
        return area;
    }

    /**
     * 方式2：遍历每一行，每一行用height[i]来装。然后
     * 分解成{@link Code84_MaxRectangleArea1}的问题，分析见笔记
     */
    public int largestRectangleArea2(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[] height = new int[col];
        int area = 0;
        //每行遍历
        for (int i = 0; i < row; i++) {
            //单独处理第i行的所有列
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    //如果当前位置为1，height++
                    height[j]++;
                } else {
                    //若当前位置为0，那么就不连续了，直接让height[j] = 0
                    height[j] = 0;
                }

            }
            //调用题目84中的方法
            area = Math.max(area, process(height));

        }
        return area;
    }

    /**
     * 方式3：使用单调栈。
     * 根据方式2的灵感，计算每个以i为最低高度的矩形面积。
     * 现在有一个栈，非递减。一开始放入-1，代表InterMinValue。
     * 从0开始放入stack。直到遇到i，其中a[i] > a[i+1]。
     * 也就是stack中对应的数组元素非递减。
     * 此时假设栈中元素为-1,m,m+1,....i。 其中a[i]>a[i+1]。
     * 现在从i开始出栈，一直到满足stack.pop >= a[i+1]。
     * 所有出栈位置i，我们计算以该位置为最低点的矩形面积。
     * s = i+1  - stack.peek - 1。
     * 遍历完毕后，最后再单独处理栈中剩余元素。
     * 这样就保证每个位置都会计算到。
     * <p>
     * 要注意：右侧比当前位置小的是i，左侧比当前位置小的是stack.peek。
     * 遍历完后，如果stack非空，右侧是a.len。
     */
    public int process(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        //非递减栈
        Stack<Integer> stack = new Stack<>();
        //注意-1位置，代表Inter.MIN_VALUE，必须要有
        stack.push(-1);
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            //对于位置i，从栈中弹出比arr[i]都大的元素，依次计算面积

            //比如弹出的是j，那么就计算以j为最底点的矩形的面积。从 j到 i -1位置
            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int cur = stack.pop();
                //第一个比arr[cur]小的位置,left到cur之间的数有可能比arr[cur]大。
                int left = stack.peek();
                int right = i;
                //从left+1到 i-1 形成的面积
                area = Math.max(area, heights[cur] * (right - left - 1));
            }
            stack.push(i);
        }
        //最后栈中元素非递减，从最后一个位置处理。最右侧是heigth.len，左侧是当前位置
        while (stack.peek() != -1) {
            int cur = stack.pop();
            //第一个比arr[cur]小的位置,left到cur之间的数有可能比arr[cur]大。
            int left = stack.peek();
            int right = heights.length;
            //从left+1到 i-1 形成的面积
            area = Math.max(area, heights[cur] * (right - left - 1));
        }
        return area;
    }


}
